package barrier;


/**
 * @author Yoni Seroussi
 * @author Roei Raviv
 *
 * No point in a barrier for 1 thread, thus assuming number of threads
 *  in barrier is at least 2 
 */
public class BinaryStaticTreeBarrier implements Barrier {

  private static final int LEFT_CHILD_ID = 1; // odd
  private static final int RIGHT_CHILD_ID = 0; // even
  private int _numOfThreads;
  private volatile boolean  _sense;
  
  ThreadLocal<Boolean> _threadSense; // thread-local sense
  ThreadLocal<Integer> _threadId; // thread-local sense
  private Node[] _node;
  
  /**
   * @param size
   */
  public BinaryStaticTreeBarrier(int size) {
    _numOfThreads = size;
    _node = new Node[size];

    _threadSense = new ThreadLocal<Boolean>() {
      @Override
      protected Boolean initialValue() { return !_sense; }
    };

    _threadId = new ThreadLocal<Integer>() {
      @Override
      protected Integer initialValue() { return ThreadID.get(); }
    };

    int depth = 0;
    
    while (size > 1) {
      depth++;
      size >>= 1;
    }
    
    // build root
    _node[0] = new Node(null);
    buildTree(depth);
  }
  
  /**
   * builds the tree as we build a heap
   * @param depth The level in the binary tree Node would be created.
   */
  public void buildTree(int depth) {
    int i;
    Node parent;
    for (i = 1; i < _numOfThreads ; i++) {
      // parent of node i
      parent = _node[getParentIdx(i)];
      // create node i
      _node[i] = new Node(parent);
      // increase counter of children
      parent.addChild();
      
      // if my child is out of the range - mark it as it is done.
      // the children counter should 
      if (getLeftChildIdx(i) > _numOfThreads - 1) {
        _node[i].markChildDone(LEFT_CHILD_ID);
      }
      if (getRightChildIdx(i) > _numOfThreads - 1) {
        _node[i].markChildDone(RIGHT_CHILD_ID);
      }
      
      //For debug:
      if ( (getLeftChildIdx(i) > _numOfThreads - 1) &&
          (getRightChildIdx(i) < _numOfThreads)) {
        throw new IllegalStateException("node " + getParentIdx(i) 
            + " has a right child but does not have left child!!!!");
      }
      
    }
  }
  
  /**
   * @param childIndex
   * @return Index of the parent of given childIndex in the node array
   */
  private int getParentIdx(int childIndex) {
    // retrun Floor( (childIndex+1)/2 - 1 )
    return ( (childIndex + 1 ) >> 1) - 1;
  }
  
  /**
   * @param parentIdx
   * @return
   */
  private int getLeftChildIdx(int parentIdx) {
    // return ((parentIdx + 1) * 2) - 1;
    int ret = ((parentIdx + 1) << 1) - 1;
//    if (ret >= _numOfThreads) {
//      // trying to access a child which does not exists
//      throw new IllegalArgumentException("Got parent Index (= " + parentIdx +
//          ") of a node which should not have left child (child idx: " + ret +
//          ")");
//    }
    return ret;
  }
  
  /**
   * @param parentIdx index of parent node in node[]
   * @return Index to the right child in node[]
   */
  private int getRightChildIdx(int parentIdx) {
    // return (parentIdx + 1) * 2;
    int ret = (parentIdx + 1) << 1;
//    if (ret >= _numOfThreads) {
//      // trying to access a child which does not exists
//      throw new IllegalArgumentException("Got parent Index (= " + parentIdx +
//          ") of a node which should not have right child (child idx: " + ret +
//          ")");
//    }
    return ret;
  }
  
  
  /**
   * Spin until all threads have reached the barrier.
   */
  @Override
  public void await() {
    _node[_threadId.get() % _numOfThreads].await();
  }

  /**
   * @author Yoni Seroussi
   * @author Roei Raviv
   *
   * NOTE: Fill in left child first. (i.e if right exists => left exists)
   */
  class Node {
    private final Byte[] PADDING = new Byte[20]; // tested on 32Bytes cacheline, reduced 2 more bytes for other class bookeeping (virtual table and such)
    // need to know IF left child is not done yet
    private volatile boolean _leftChildNotDone; // all even thread ids (assume 1 Bytes)
    // need to know IF right child is not done yet
    private volatile boolean _rightChildNotDone; // all odd thread ids 
    final Node _parent; // (4Bytes)
    int _children; // number of children   (4Bytes)
    
    public Node(Node parent) {
      _parent = parent;
      _rightChildNotDone = true;
      _leftChildNotDone = true;
    }
    
    public void await() {
      boolean mySense = _threadSense.get();
      int me = _threadId.get();
//    if (_children > 0) {
//    // wait for left/right child if exists
//      while (_leftChildNotDone) {}
//      _leftChildNotDone = false; // mark for next phase
//      
//      while (_rightChildNotDone) {}
//      _rightChildNotDone = false; // mark for next phase
//  }
//
      // wait for left/right child if exists
      switch (_children) {
      case 2:
        while (_rightChildNotDone) {}
        _rightChildNotDone = true; // mark for next phase
        // no break on purpuse
      case 1: 
        while (_leftChildNotDone) {}
        _leftChildNotDone = true; // mark for next phase
        break;
      default:
        break;
      }
  
      if (_parent == null) { // root?
        _sense = !_sense;   // am root: toggle global sense
      } else {
        _parent.markChildDone(me); // indicate child subtree completion
        while (_sense != mySense) {}; // wait for global sense to change
      }
      
      _threadSense.set(!mySense); // toggle sense
    }
    
    /**
     * @param childThreadId Thread ID of the caller.
     * 
     * TODO - code might be faster if we put _<side>ChildNotDone as package
     * visibility and let each child access its parent fields and update them
     * without calling a method. (we must have access to parent so we exit our
     * local cache
     */
    public void markChildDone(int childThreadId) {
      if (childThreadId % 2 == 0) {
        _rightChildNotDone = false;
      } else {
        _leftChildNotDone = false;
      }
    }

    /**
     * Increments 
     */
    void addChild() {
      _children++;
      // Perform check (this should be called only during the tree building 
      // process so we don't care it takes a little longer.
      if (_children > 2) {
        throw new IllegalStateException("ERROR: Parent has more than 2" +
        		"children in a Binary tree");
      }
    }
  }
  
}
